645E - Intellectual Inquiry - CodeForces Solution

// author: gary

// created: 2018/04/21 15:28:31

#include <cassert>

#include <cctype>

#include <climits>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <limits>

#include <utility>

#include <functional>

#include <string>

#include <bitset>

#include <deque>

#include <list>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <vector>

#include <algorithm>

#include <iostream>

#include <sstream>

using namespace std;

#define SZ(x) ( (int) (x).size() )

#define ALL(c) (c).begin(), (c).end()

#define CNT(c, x) ((c).find(x) != (c).end())

typedef pair<int, int> pii;

typedef long long ll;

template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }

template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

void madd(int& a, int b) {

  a += b;

  if(a >= mod)

    a -= mod;

}



int mul(int a, int b) {

  return (1LL * a * b) % mod;

}



int add(int a, int b) {

  return (a + b) % mod;

}



int sub(int a, int b) {

  return (a - b + mod) % mod;

}



int mpow(int a, int n) {

  int r = 1;

  while(n > 0) {

    if(n & 1)

      r = mul(r, a);

    a = mul(a, a);

    n >>= 1;

  }

  return r;

}



int n, m, sigma, tot;

int last[N], L[N], p[N];

char s[N];



int main() {

  scanf("%d%d%s", &n, &sigma, s);

  m = strlen(s);



  tot = 1;

  memset(last, -1, sizeof last);

  for(int i = 0; i < m; i++) {

    int c = s[i] - 'a';

    int tmp = sub(tot, L[c]);

    L[c] = tot;

    madd(tot, tmp);

    last[c] = i;

  }



  for(int i = 0; i < sigma; i++) {

    p[i] = i;

  }

  auto byLast = [&] (int i, int j) -> bool {

    return last[i] < last[j];

  };

  sort(p, p + sigma, byLast);



  for(int i = 0; i < n; i++) {

    int j = p[i % sigma];

    int tmp = sub(tot, L[j]);

    L[j] = tot;

    madd(tot, tmp);

  }



  printf("%d\n", tot);

  return 0;

}